package com.wish.algorithm.sort;

import com.wish.inter.algorithm.ISort;

import java.util.Arrays;

/**
 * Created by suliucheng on 2021/4/19 9:36
 * Directions:插入排序
 * 插入排序的思想就是 把数组看成一个有序和一个无序的两部分 例如：3 2 1 0 4
 * 第一次插  有序部分 3  无序部分 2 1 0 4 把无序部分的第一个数字2插入到3前面
 * 第二次插  有序部分 2 3 无序部分  1 0 4 把无序部分的第一个数字1插入到 2 3前面
 * 第三次插  有序部分1 2 3 无序部分   0 4 把无序部分的第一个数字0插入到1 2 3前面
 * 第四次插  有序部分0 1 2 3 无序部分 4 把无序部分的第一个数字4插入到1 2 3后面
 * 得到： 1 2 3 4
 */
public class Insert implements ISort {

    /**
     * @param arr 传入的无序数组
     * @return
     */
    @Override
    public int[] sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            while (j > 0){
                if (arr[j] < arr[j-1]){
                    int temp ;
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                    j--;
                }else {
                    break;
                }
            }
        }
        return arr;
    }
}

